{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from math import sqrt\n",
    "from collections import Counter\n",
    "\n",
    "def kNN_classify(k, X_train, y_train, x):\n",
    "    assert 1 <= k <= X_train.shape[0], \"k must be valid\"\n",
    "    assert X_train.shape[0] == y_train.shape[0], \"the size of X_train must equal to the size of y_train\"\n",
    "    assert X_train.shape[1] == x.shape[0], \"the feature number of x must be equal to X_train\"\n",
    "    \n",
    "    distances = [sqrt(np.sum((x_train-x)**2)) for x_train in X_train]\n",
    "    nearst = np.argsort(distances)\n",
    "    \n",
    "    topK_y = [y_train[i] for i in nearst[:k]]\n",
    "    votes = Counter(topK_y)\n",
    "    \n",
    "    return votes.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(666)\n",
    "raw_data_X = np.random.rand(20).reshape(10, -1)\n",
    "np.random.seed(666)\n",
    "raw_data_y = np.random.randint(0, 2, 10)\n",
    "\n",
    "X_train = raw_data_X\n",
    "y_train = raw_data_y\n",
    "\n",
    "np.random.seed(666)\n",
    "x = np.random.rand(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kNN_classify(6, X_train, y_train, x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用scikit-learn中的kNN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "kNN_classifier = KNeighborsClassifier(n_neighbors=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
       "                     metric_params=None, n_jobs=None, n_neighbors=6, p=2,\n",
       "                     weights='uniform')"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kNN_classifier.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "Expected 2D array, got 1D array instead:\narray=[0.70043712 0.84418664].\nReshape your data either using array.reshape(-1, 1) if your data has a single feature or array.reshape(1, -1) if it contains a single sample.",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-29-bd5f1db77c95>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mkNN_classifier\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpredict\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\lib\\site-packages\\sklearn\\neighbors\\classification.py\u001b[0m in \u001b[0;36mpredict\u001b[1;34m(self, X)\u001b[0m\n\u001b[0;32m    145\u001b[0m             \u001b[0mClass\u001b[0m \u001b[0mlabels\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0meach\u001b[0m \u001b[0mdata\u001b[0m \u001b[0msample\u001b[0m\u001b[1;33m.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    146\u001b[0m         \"\"\"\n\u001b[1;32m--> 147\u001b[1;33m         \u001b[0mX\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mcheck_array\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0maccept_sparse\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;34m'csr'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    148\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    149\u001b[0m         \u001b[0mneigh_dist\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mneigh_ind\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mkneighbors\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\lib\\site-packages\\sklearn\\utils\\validation.py\u001b[0m in \u001b[0;36mcheck_array\u001b[1;34m(array, accept_sparse, accept_large_sparse, dtype, order, copy, force_all_finite, ensure_2d, allow_nd, ensure_min_samples, ensure_min_features, warn_on_dtype, estimator)\u001b[0m\n\u001b[0;32m    519\u001b[0m                     \u001b[1;34m\"Reshape your data either using array.reshape(-1, 1) if \"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    520\u001b[0m                     \u001b[1;34m\"your data has a single feature or array.reshape(1, -1) \"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 521\u001b[1;33m                     \"if it contains a single sample.\".format(array))\n\u001b[0m\u001b[0;32m    522\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    523\u001b[0m         \u001b[1;31m# in the future np.flexible dtypes will be handled like object dtypes\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mValueError\u001b[0m: Expected 2D array, got 1D array instead:\narray=[0.70043712 0.84418664].\nReshape your data either using array.reshape(-1, 1) if your data has a single feature or array.reshape(1, -1) if it contains a single sample."
     ]
    }
   ],
   "source": [
    "kNN_classifier.predict(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.70043712, 0.84418664]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_predict = x.reshape(1, -1)\n",
    "X_predict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kNN_classifier.predict(X_predict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_predict = kNN_classifier.predict(X_predict)\n",
    "y_predict[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 重新整理我们的kNN的代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from math import sqrt\n",
    "from collections import Counter\n",
    "\n",
    "class kNNClassifier:\n",
    "    \n",
    "    def __init__(self, k):\n",
    "        \"\"\"初始化kNN分类器\"\"\"\n",
    "        assert k >= 1, \"K must be valid!\"\n",
    "        self.k = k\n",
    "        self._X_train = None\n",
    "        self._y_train = None\n",
    "        \n",
    "    def fit(self, X_train, y_train):\n",
    "        \"\"\"根据训练数据集X_train和y_train训练kNN分类器\"\"\"\n",
    "        assert X_train.shape[0] == y_train.shape[0], \"the size of X_train must equal to the size of y_train\"\n",
    "        assert self.k <= X_train.shape[0], \"the size of X_train must be at least k\"\n",
    "    \n",
    "        self._X_train = X_train\n",
    "        self._y_train = y_train\n",
    "        return self\n",
    "    \n",
    "    def predict(self, X_predict):\n",
    "        \"\"\"给定待预测数据集X_predict, 返回表示X_predict的结果向量\"\"\"\n",
    "        assert self._X_train is not None and self._X_train is not None, \"must fit before predict\"\n",
    "        assert self._X_train.shape[1] == X_predict.shape[1], \"the feature number of X_predict must be equal to X_train\"\n",
    "        \n",
    "        y_predict = [self._predict(x) for x in X_predict]\n",
    "        return np.array(y_predict)\n",
    "    \n",
    "    def _predict(self, x):\n",
    "        \"\"\"给定单个待测数据x，返回x的预测结果\"\"\"\n",
    "        assert self._X_train.shape[1] == x.shape[0], \"the feature number of x must be equal to X_train\"\n",
    "        \n",
    "        distances = [sqrt(np.sum((x_train-x)**2)) for x_train in self._X_train]\n",
    "        nearst = np.argsort(distances)\n",
    "    \n",
    "        topK_y = [self._y_train[i] for i in nearst[:self.k]]\n",
    "        votes = Counter(topK_y)\n",
    "    \n",
    "        return votes.most_common(1)[0][0]\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"KNN(k=%d)\" % self.k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_clf = kNNClassifier(k=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KNN(k=6)"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn_clf.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_predict = knn_clf.predict(X_predict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0])"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_predict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_predict[0]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
